I. Field of the Invention
The current invention relates to wireless communications. More particularly, the present invention relates to an improved method and system for reliably transmitting data through a wireless channel while minimizing the overhead inherent in the error control protocol.
II. Description of the Related Art
The use of code division multiple access (CDMA) modulation techniques is one of several techniques for facilitating communications in which a large number of system users are present. Other multiple access communication system techniques, such as time division multiple access (TDMA), frequency division multiple access (FDMA) and AM modulation schemes such as amplitude companded single sideband (ACSSB) are known in the art. These techniques have been standardized to facilitate interoperation between equipment manufactured by different companies. Code division multiple access communications systems have been standardized in the United States in Telecommunications Industry Association TIA/EIA/IS-95-B, entitled xe2x80x9cMOBILE STATION-BASE STATION COMPATIBILITY STANDARD FOR DUAL-MODE WIDEBAND SPREAD SPECTRUM CELLULAR SYSTEMSxe2x80x9d, incorporated by reference herein, and hereinafter referred to as IS-95.
IS-95 was originally optimized for transmission of variable-rate voice frames. In order to support two-way voice communications, as typified in wireless phone applications, it is desirable that a communication system provide fairly constant and minimal data delay. For this reason, IS-95 systems are designed with powerful forward error correction (FEC) protocols and vocoders which are designed to respond gracefully to voice frame errors. Error control protocols which require frame retransmission procedures add unacceptable delays to voice transmission, so are not designed into the IS-95 specification.
The optimizations which make the standalone IS-95 specification ideal for voice applications make it difficult to use for packet data applications. In many non-voice applications, such as the transmission of Internet protocol (IP) data, the delay requirements of the communication system are much less stringent than in voice applications. In the Transmission Control Protocol (TCP), probably the most prevalent of protocols used in an IP network, virtually infinite transmission delays are allowed in order to guarantee error-free transmission. TCP uses retransmissions of IP datagrams, as IP packets are commonly called, to provide this transport reliability.
IP datagrams are generally too large to fit into a single IS-95 frame. Even after dividing an IP datagram into segments small enough to fit into a series of IS-95 frames, an entire series of IS-95 frames would have to be received without error for the single IP datagram to be useful to TCP. The frame error rate typical of an IS-95 system make the probability of error-free reception of all segments of a single datagram very low.
As described in IS-95, alternative service options enable the transmission of other types of data in lieu of voice frames. The TIA/EIA/IS-707-A, entitled xe2x80x9cDATA SERVICE OPTIONS FOR SPREAD SPECTRUM SYSTEMSxe2x80x9d, hereafter referred to as IS-707, describes procedures used in the transmission of packet data in an IS-95 system.
Radio Link Protocol (RLP) is described in TIA/EIA/IS-707-A.8, entitled xe2x80x9cDATA SERVICE OPTIONS FOR SPREAD SPECTRUM SYSTEMS: RADIO LINK PROTOCOL TYPE 2xe2x80x9d, hereinafter referred to as RLP2, and incorporated herein by reference. RLP2 incorporates an error control protocol with frame retransmission procedures over the IS-95 frame layer. RLP is of a class of error control protocols known as NAK-based ARQ protocols, which are well known in the art. The IS-707 RLP, facilitates the transmission of a byte-stream, rather than a series of voice frames, through an IS-95 communication system.
Several protocol layers typically reside above the RLP layer. IP datagrams, for example, are typically converted into a Point-To-Point Protocol (PPP) byte stream before being presented as a byte stream to the RLP protocol layer. As the RLP layer ignores the protocol and framing of higher protocol layers, the stream of data transported by RLP is said to be a xe2x80x9cfeatureless byte streamxe2x80x9d.
RLP was originally designed to satisfy the requirements of sending large frames through an IS-95 channel. For example, if an IP datagram of 500 bytes were to be simply sent in IS-95 frames carrying 20 bytes each, the IP datagram would fill 25 consecutive IS-95 frames. Without some kind of error control layer, all 25 of these frames would have to be received without error in order for the IP datagram to be useful to higher protocol layers. On an IS-95 channel having a 1% frame error rate, the effective error rate of the IP datagram delivery would be (1xe2x88x92(0.99)25), or 22%. This is a very high error rate compared to most networks used to carry Internet Protocol traffic. RLP was designed as a link layer protocol which would decrease the error rate of IP traffic to be comparable to the error rate typical of a 10Base2 ethernet channel.
The International Telecommunications Union recently requested the submission of proposed methods for providing high rate data and high-quality speech services over wireless communication channels. A first of these proposals was issued by the Telecommunications Industry Association, entitled xe2x80x9cThe cdma2000 ITU-R RTT Candidate Submissionxe2x80x9d, and hereinafter referred to as cdma2000. A second of these proposals was issued by the European Telecommunications Standards Institute (ETSI), entitled xe2x80x9cThe ETSI UMTS Terrestrial Radio Access (UTRA) ITU-R RTT Candidate Submissionxe2x80x9d, also known as xe2x80x9cwideband CDMAxe2x80x9d and hereinafter referred to as W-CDMA. A third proposal was submitted by U.S. TG 8/1 entitled xe2x80x9cThe UWC-136 Candidate Submissionxe2x80x9d, hereinafter referred to as EDGE. The contents of these submissions are public record and are well known in the art.
RLP2 is optimized for use with IS-95B, in which the rate set, derived from channel capacity, and used during a packet data call remains essentially fixed for the duration of the call. Based on this assumption of fixed rate sets, RLP2 is designed with the assumption that retransmitted RLP frames can be sent within a maximum of three consecutive RLP segments. The probability that one of three segments is lost, causing the loss of a retransmitted RLP frame, has been deemed acceptable by the designers of RLP2.
In cdma2000, however, the channel capacity available to a single user, and hence the maximum data rate used during a packet data call, can vary widely and rapidly. For example, during the course of a single cdma2000 call, the supplemental channel capacity used by a packet data service option may vary from 9.6 kilo-bits per second (kbps) to more than 307 kbps. In a simple extension of the RLP2, the maximum number of segments used during retransmissions could be increased as necessary to accommodate the change in data rates. Because the capacity of a call channel may diminish during a call, a full-rate frame transmitted unsuccessfully at a high rate might span 30 or more consecutive lower-rate-set cdma2000 segments. The high likelihood that one or more of those cdma2000 segments makes such a simple extension of the RLP2 largely impractical for use with cdma2000.
RLP2 has been optimized to require minimal protocol overhead space over the two IS-95 rate sets, known as Rate Set 1 (RS1) and Rate Set 2 (RS2). The RLP frame sequence numbers in RLP2 are 8 bits long, a size which is ideal for computer processing. Since the rate sets specified in cdma2000 include RS1 and RS2, it would be highly desirable for an RLP designed for cdma2000 (RLP2000) to be at least as efficient as RLP2 mwhen used at RS1 and RS2. Because switching RLP protocols whenever the rate set changes would add complexity to RLP2000, it is desirable that a single RLP2000 protocol efficiently support RS1, RS2, and all the higher cdma2000 data rates without requiring resynchronization or substantial protocol complexity.
The present invention may be used to design an enhanced RLP to enable efficient transmission of a featureless byte stream through a channel of varying capacity. An exemplary embodiment of the invention is as efficient as RLP2 when used over a channel having the same capacity as IS-95 RS1 and RS2. At the same time, an enhanced RLP, designed in accordance with the current invention, also enables efficient transmission of data at varying channel capacities up to and exceeding the maximum specified in cdma2000. The present invention is applicable to any communication system employing transmission of a byte stream over a wireless channel. The present invention is applicable to systems such as cdma2000, W-CDMA, and EDGE, wherein a byte stream may be carried within over-the-air frames specified for use by the wireless communication system.
The efficiency of the embodiments of the invention at varying rates is made possible by changing the interpretation of the sequence numbers carried in the RLP protocol header. In RLP2, sequence numbers are used to denote frame numbers. This is appropriate for RLP2, as the channel capacity used in a packet data call, and hence the maximum number of data bytes carried in a full-rate frame, are both constant. RLP2 uses a one-byte frame sequence number, and frames are transmitted at 20 millisecond (ms) intervals. When an RLP2 frame is lost during transmission, the data of the lost frame is segmented into as many as three retransmit segments, each having the same sequence number as the original lost frame.
In trying to adapt RLP2 for use over channels with widely varying capacity, difficulty arises when a frame transmitted on a high-capacity channel (for example, 307 kbps) must be retransmitted on a low-capacity channel (for example, 9.6 kbps). Using a frame interval of 20 ms, a full-rate frame on a 307 kbps channel could carry as many as 750 bytes of data. Such a frame could be lost during transmission, and at the same time, the channel capacity might be reduced to 9.6 kbps. In RLP2, the capacity of a 9.6 kbps full-rate 20 ms frame is 20 bytes. In a simple extension of the maximum allowable retransmission segments, successful retransmission of a single frame of 750 bytes of data would require successful transmission of approximately 38 consecutive 9.6 kbps full-rate RLP2 retransmit segments. Because all retransmit segments would have the same sequence number, the loss of one of those 38 retransmit segments would cause the loss of the entire retransmitted frame. The receiver could not negatively-acknowledge (NAK) individual retransmit segments. If the over-the-air frame error rate were 1%, the probability of successful transmission of 38 consecutive full-rate RLP2 retransmit segments would be approximately 68%. In this scenario, the retransmission of the segments would often fail, causing data loss and a break in the byte stream due to RLP2 resynchronization. Thus, such a simple extension of RLP2 would frequently result in lost data whenever a high-capacity full-rate frame had to be retransmitted over a low-capacity channel.
One way to accomplish more reliable data retransmission would be to use a byte sequence number in the RLP header instead of a frame sequence number. Then, upon the loss of a large, high-rate RLP frame followed closely by a decrease in channel capacity, the data in the lost frame could be divided into small, independent RLP retransmit frames. The receiver would not be required to receive 38 consecutive retransmit frames without error. The receiver could accept whichever retransmit frames it successfully received and simply negatively acknowledge (NAK) any lost retransmitted frames. Again using an over-the-air frame error rate of 1%, the probability of the same retransmit segment being lost twice in a row would be 0.01%.
One disadvantage of using a byte sequence number instead of a frame sequence number is the larger number of bits in a byte sequence number to represent the same data. If a byte sequence number were used in a 9.6 kbps full-rate RLP2 frame, the sequence number would have to be 5 bits longer than the 8-bit frame sequence number. In cdma2000, where channel capacity may vary from 9.6 kbps to 32 times that capacity (approximately 307 kbps), a full-rate 307 kbps frame could carry as many as 750 RLP data bytes. The number of byte sequence number bits necessary to track the same duration of 20-millisecond frames as in RLP2 is at least 18 bits. To make room for an 18-bit byte sequence number in a 9.6 kbps RLP frame, the frame would be able to carry two fewer data bytes, a decrease of 10%.
The embodiments of the invention provide the benefits of large byte sequence numbers while transmitting a fraction of the sequence number bits in the majority of over-the-air frames. In one embodiment of the invention, a 20-bit byte sequence number is used to track received data. The number of bytes which may be tracked with a sequence number is called the sequence number space. In the case of a 20-bit sequence number, the size of the sequence number space is 220.
Gaining the benefits of a large sequence number without adding to the average frame header size is accomplished by carefully selecting portions of the sequence number space which will go unassigned to transmitted data bytes. In other words, some of the sequence number space will not be used to track actual transmitted bytes, and may be viewed as wasted. The size of the sequence number is chosen such that wastage of the sequence number space is permissible without impacting the performance of the protocol. For example, if an 18-bit sequence number is necessary to endure a 5-second transmission loss on a 307 kbps channel, the use of a 20-bit sequence number allows three fourths of the sequence number space to go unused without impacting the maximum allowable length of transmission loss.
The unused portion of sequence number space is chosen such that the first byte of each new transmitted data frame starts at a predetermined distance, called a page size, from the first byte of the previous data frame. For example, if the first byte in frame n has a sequence number of 1000, and the page size is 100, the first byte of frame n+1 will start on the next page with a sequence number of 1100. If frame n only carries 40 bytes, numbered 1000 to 1039, then the sequence number space from 1040 to 1099 would go unused. The motivation to allow the seeming waste of sequence number space allows a decrease in the bit size of the sequence number sent in the frame. In the example just shown, the sequence number could be divided by 100 before inserting it into the frame, and could therefore be represented by at least 6 fewer bits. In a preferred embodiment of the invention, page sizes are powers of 2, such as 64, to facilitate computer software manipulation of sequence numbers.
In the previously described scenario, in which a 750 data bytes in a high-rate frame are lost, the preferred embodiment of the invention easily adapts to retransmission on high capacity and low capacity channels alike. In a high capacity channel, the data is easily retransmitted in one or two retransmit frames. If, however, the capacity of the channel has decreased, the data bytes to be retransmitted are divided among several independent retransmit frames, each having its own sequence number. The use of independent retransmit sequence numbers has advantages over the segmented retransmission specified by RLP2. If a single RLP2 retransmit segment is lost in transmission, then all the segments carrying the same sequence number must be again retransmitted in order to recover the data of the lost segment. In contrast, if one or more of the independently-numbered retransmit frames are lost in transmission, the receiver can negatively-acknowledge (NAK) the individual, lost retransmit frame. After receiving the second NAK, the transmitter may send the individual retransmit frame for a second time. Again, using an over-the-air frame error rate of 1%, the probability of the same retransmit frame being lost twice in a row is 0.01%. RLP resynchronization, its associated data loss, and byte stream discontinuity, is rarely necessary.
One disadvantage of using sequence numbers corresponding to bytes instead of frames is that more bits are generally needed to represent the sequence number. This can cause a slight increase in the number of independently-numbered retransmit frames needed to carry the data of a lost frame. In an exemplary embodiment of the invention, however, this impact is minimized by sometimes omitting most significant and least significant bits from the sequence number.